package imganalysis;

import iautils.IAUtils;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 *
 * @author sheila
 */
public class KMeans {
    private ArrayList <DataUnit> aAllDataUnits;
    private ArrayList <Cluster> aClusters;
    private int inumClusters;
    ArrayList <int []> aNewCentroids = new ArrayList<int []>();
    int numDimensions=128;
   
    public KMeans(ArrayList<int []> paAllDimensionsVectors, int pnumClusters,int idImage){ //uso a primeira vez
        int [] tmpDimensionVector;
        this.aAllDataUnits = new ArrayList<DataUnit>();
        for (int iCurrentDimVector = 0; iCurrentDimVector < paAllDimensionsVectors.size(); iCurrentDimVector++) {
            tmpDimensionVector = paAllDimensionsVectors.get(iCurrentDimVector);
            this.aAllDataUnits.add(new DataUnit( iCurrentDimVector, tmpDimensionVector ));
        }
        run(pnumClusters, idImage);
    }

    public KMeans(int pnumClusters, ArrayList <DataUnit> paAllDataUnits, int idImage){
        this.aAllDataUnits = paAllDataUnits;
        run(pnumClusters, idImage);
    }

    public void run(int pnumClusters, int idImage){
        this.aClusters=new ArrayList<Cluster>();
        this.inumClusters = pnumClusters;
        //*********************** Algorithm ************************************        
        this.initializeClusters(idImage); //Creates clusters with random centroids
        long tempoInicial = System.currentTimeMillis();
        do{
            if(!this.aNewCentroids.isEmpty()){
                this.moveChangingCentroids();
            }
            this.groupDataUnitsIntoClusters();
            this.recomputeCentroids();            
        } while(hasCentroidsChanged());
        long tempoFinal = System.currentTimeMillis();
        System.out.println( "Tempo de execução" + ((tempoFinal - tempoInicial)*0.001)+ " segundos" );
        //for (int j = 0; j < inumClusters; j++) {System.out.println("=Elementos no cluster "+j+" es: "+this.getAClusters().get(j).getNumDataUnits());  }
    }


    public void initializeClusters(int idImg){
        int [] aiCentroid= this.aAllDataUnits.get(idImg).cloneAiDimensionsVector();
        this.aClusters.add(  new Cluster(aiCentroid)  );

        for (int i = 1; i < inumClusters; i++) {
            int index = (int) Math.round( Math.random() * (this.aAllDataUnits.size()-1)  );
            aiCentroid= this.aAllDataUnits.get(index).cloneAiDimensionsVector();
            this.aClusters.add(  new Cluster(aiCentroid)  );
        }
    }
    
    public boolean hasCentroidsChanged(){
        for (int indexCurrentCluster = 1; indexCurrentCluster < this.aClusters.size(); indexCurrentCluster++) {
            Cluster oCurrentCluster = this.aClusters.get(indexCurrentCluster);
            if(IAUtils.compareHistograms(oCurrentCluster.getAiCentroidDimensionsVector(),this.aNewCentroids.get(indexCurrentCluster))  >  0 )
                return true;
        }
        return false;
    }
    public void moveChangingCentroids(){
        for (int indexCurrentCluster = 1; indexCurrentCluster < this.aClusters.size(); indexCurrentCluster++) {
            Cluster oCurrentCluster = this.aClusters.get(indexCurrentCluster);
            if(IAUtils.compareHistograms(oCurrentCluster.getAiCentroidDimensionsVector(),this.aNewCentroids.get(indexCurrentCluster))  >  0 ){
                for (int i = 0; i < numDimensions; i++)
                    oCurrentCluster.setCentroidDimension( i, this.aNewCentroids.get(indexCurrentCluster)[i]);
            }
        }
    }

    /**
     * Computing the nearest Cluster for every DataUnit
     */
    public void groupDataUnitsIntoClusters(){        
        for (int i = 0; i < this.aClusters.size(); i++) {
            this.aClusters.get(i).removeAllDataUnits();
        }
        
        int iDst=10000, dstMinimun=10000, tmpIndexCluster=-1;
        for (int indexcurrentDataUnit = 0; indexcurrentDataUnit < this.aAllDataUnits.size(); indexcurrentDataUnit++) {
            DataUnit oCurrentDataUnit = aAllDataUnits.get(indexcurrentDataUnit);
            dstMinimun=10000;
            for (int indexCurrentCluster = 0; indexCurrentCluster < this.aClusters.size(); indexCurrentCluster++) {
                iDst = IAUtils.compareHistograms(oCurrentDataUnit.getAiDimensionsVector(), aClusters.get(indexCurrentCluster).getAiCentroidDimensionsVector());
                if(iDst < dstMinimun){
                    dstMinimun = iDst;
                    tmpIndexCluster = indexCurrentCluster;
                }
            }
            this.aClusters.get(tmpIndexCluster).addDataUnit(oCurrentDataUnit);          
        }
    }

    public void recomputeCentroids(){         
        int iDst;        
        aNewCentroids.clear();
        // it's not necessary to recompoute the centroid of the first cluster because it's always the same: query image
        aNewCentroids.add(0,aClusters.get(0).getAiCentroidDimensionsVector());
        for (int indexCurrentCluster = 1; indexCurrentCluster < this.aClusters.size(); indexCurrentCluster++) {
            Cluster oCurrentCluster = this.aClusters.get(indexCurrentCluster);
            int[] aiNewCentroidDimVector=new int[numDimensions];

            // the new centroid is initialized with 0. It has not data units. its a bad centroid
            if(oCurrentCluster.getNumDataUnits()==0)
                for(int i=0;i<numDimensions;i++) aiNewCentroidDimVector[i] = 0;
            
            for(int indexCurrentDataUnit = 0; indexCurrentDataUnit < oCurrentCluster.getNumDataUnits(); indexCurrentDataUnit++) {               
                for(int i=0;i<numDimensions;i++)
                    aiNewCentroidDimVector[i] += oCurrentCluster.getDataUnit(indexCurrentDataUnit).getDimension(i);
            }

            for (int j = 0; j < aiNewCentroidDimVector.length && oCurrentCluster.getNumDataUnits()>0 ; j++)
                aiNewCentroidDimVector[j] = aiNewCentroidDimVector[j] / oCurrentCluster.getNumDataUnits();
            
            aNewCentroids.add(indexCurrentCluster,aiNewCentroidDimVector);
        }
    }

    public ArrayList<Cluster> getAClusters() {
        return aClusters;
    }
        public void printCentroidClusters(int [] aiDimensionVector){
        for (int i = 0; i < numDimensions; i++)
            System.out.print(" - "+aiDimensionVector[i]);
        System.out.println("");
    }


    public void orderingDataUnits(int idCluster) {
        final Cluster oCurrentCluster=this.aClusters.get(idCluster);
        SortedMap sm=new TreeMap(new Comparator() {
            public int compare(Object o1, Object o2) {
                int iDstO1 = IAUtils.compareHistograms(((DataUnit)o1).getAiDimensionsVector(), oCurrentCluster.getAiCentroidDimensionsVector());
                int iDstO2 = IAUtils.compareHistograms(((DataUnit)o2).getAiDimensionsVector(), oCurrentCluster.getAiCentroidDimensionsVector());
                return (iDstO1<iDstO2)?-1:+1;
            }
        });

        for (int i = 0; i < oCurrentCluster.getNumDataUnits(); i++)
            sm.put(oCurrentCluster.getDataUnit(i), 0);
        
        oCurrentCluster.removeAllDataUnits( );
        Iterator iterator = sm.keySet().iterator();
        while (iterator.hasNext()) {
          Object key = iterator.next();
          oCurrentCluster.addDataUnit((DataUnit)key);
        }
    }

    /**
     * Cluster ordering by considering the distance from their respective
     * centroids to the DataUnit with the given id.
     * @param id - Id of the DataUnit that determine the order of Clusters. (QueryImage)
     */
    public void orderingClustersByCentroid(int id)
    {
        DataUnit oCurrentDataUnit=this.aAllDataUnits.get(id);
        SortedMap sm=new TreeMap(new Comparing(oCurrentDataUnit));
               
        for (int indexCurrentCluster = 0; indexCurrentCluster < this.aClusters.size(); indexCurrentCluster++) {
            sm.put(aClusters.get(indexCurrentCluster), 0);
        }
        this.aClusters.clear();
        
        Iterator iterator = sm.keySet().iterator();
        while (iterator.hasNext()) {
          Object key = iterator.next();
          this.aClusters.add((Cluster)key);
          //System.out.println("key : " + key + " value :" + map.get(key));
        }
    }

    public class Comparing implements Comparator{
        DataUnit oCurrentDataUnit;
        public Comparing(DataUnit poCurrentDataUnit ){
            this.oCurrentDataUnit = poCurrentDataUnit;
        }
        
        /*
         * It is compared the cluster centroid with the query image. A cluster is located before another if its similarity with the query image is bigger.
         * Finally we obtain a Map of clusters ordered according to the similarity of the respective clusters centroids to the query image.
         */
        public int compare(Object o1, Object o2) {
            int iDstO1 = IAUtils.compareHistograms(((Cluster)o1).getAiCentroidDimensionsVector(), oCurrentDataUnit.getAiDimensionsVector());
            int iDstO2 = IAUtils.compareHistograms(((Cluster)o2).getAiCentroidDimensionsVector(), oCurrentDataUnit.getAiDimensionsVector());
            return (iDstO1<iDstO2)?-1:+1;
        }
    }
}